Synonymous sentence [Union Find]

Time: O(PxLxLog(PxL)); Space: O(PxL); medium

Given a list of pairs of equivalent words synonyms and a sentence text,

return all possible synonymous sentences sorted lexicographically.

Example 1:

Input: synonyms = [[“happy”,“joy”],[“sad”,“sorrow”],[“joy”,“cheerful”]], text = “I am happy today but was sad yesterday”

Output:

["I am cheerful today but was sad yesterday",
 "I am cheerful today but was sorrow yesterday",
 "I am happy today but was sad yesterday",
 "I am happy today but was sorrow yesterday",
 "I am joy today but was sad yesterday",
 "I am joy today but was sorrow yesterday"
]

Constraints:

  • 0 <= len(synonyms) <= 10

  • len(synonyms[i]) == 2

  • synonyms[0] != synonyms[1]

  • All words consist of at most 10 English letters only.

  • text is a single space separated sentence of at most 10 words.

[6]:

class UnionFind(object):
    def __init__(self, n):
        self.set = [x for x in range(n)]
        self.count = n

    def find_set(self, x):
        if self.set[x] != x:
            self.set[x] = self.find_set(self.set[x])  # path compression.
        return self.set[x]

    def union_set(self, x, y):
        x_root, y_root = list(map(self.find_set, (x, y)))
        if x_root == y_root:
            return False
        self.set[max(x_root, y_root)] = min(x_root, y_root)
        return True

[7]:

import collections
import itertools

class Solution1(object):
    """
    Time: O(P*L*Log(P*L)), P is the production of all number of synonyms, L is the length of a word
    Space: O(P*L)
    """
    def generateSentences(self, synonyms, text):
        """
        :type synonyms: List[List[str]]
        :type text: str
        :rtype: List[str]
        """
        def assign_id(x, lookup, inv_lookup):
            if x in lookup:
                return
            lookup[x] = len(lookup)
            inv_lookup[lookup[x]] = x

        lookup, inv_lookup = {}, {}
        for u, v in synonyms:
            assign_id(u, lookup, inv_lookup), assign_id(v, lookup, inv_lookup)
        union_find = UnionFind(len(lookup))
        for u, v in synonyms:
            union_find.union_set(lookup[u], lookup[v])
        groups = collections.defaultdict(list)
        for i in range(len(union_find.set)):
            groups[union_find.find_set(i)].append(i)
        result = []
        for w in text.split(' '):
            if w not in lookup:
                result.append([w])
                continue
            result.append(sorted(map(lambda x: inv_lookup[x],
                                 groups[union_find.find_set(lookup[w])])))

        return [" ".join(sentense) for sentense in itertools.product(*result)]

[8]:

s = Solution1()

synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]]
text = "I am happy today but was sad yesterday"
assert s.generateSentences(synonyms, text) == [
  "I am cheerful today but was sad yesterday",
  "I am cheerful today but was sorrow yesterday",
  "I am happy today but was sad yesterday",
  "I am happy today but was sorrow yesterday",
  "I am joy today but was sad yesterday",
  "I am joy today but was sorrow yesterday"
]